package edu.kmust.simple;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * @author： 常伟
 * @create： 2018/7/23 20:41
 * @email： kmustchang@qq.com
 * @version: 1.0
 * @Description： 第一题：狼羊菜过河问题
 *      一个人在河边，带着一匹狼、一只羊和一颗卷心菜。他需要用船将这三样东西运至对岸，然而，这艘船的空间有限，只容得下他自己和
 *      另一样东西（或狼或羊或卷心菜）。若他不在场看管的话，狼就回去吃羊，羊就回去吃卷心菜。此人如何才能把这三个“乘客”都运至
 *      对岸。
 */
public class ExaminationOne01 {

    /**
     * 这个表示终止状态（结束状态）
     */
    private static final int END_STATE=15;

    /**
     * 这个表示最初状态（开始状态）
     */
    private static final int BGEIN_STATE=0;

    /**
     * 这个表示结果
     */
    private List<List<Integer>> result=new ArrayList<>();

    /**
     * 这个表示从开始状态到目前的序列，这个序列还有一个作用，就是用于避免重复。
     * 避免将重复的状态加入进来。
     */
    private List<Integer> sequence=new ArrayList<>();

    /**
     * 用来表示当前的状态，
     *      0表示人
     *      1表示狼
     *      2表示羊
     *      3表示卷心菜
     *      因为船始终和人在一起，所以就将船和人用一个来表示
     *      value   
     *              0表示在河岸
     *              1表示在河对岸
     *      即state[0]=0就表示人在河岸，state[2]=1表示羊在河对岸。
     */
    private int[] state=new int[4];
    
    public static void main(String[] args) {
        ExaminationOne01 examination_one_01=new ExaminationOne01();
        examination_one_01.sequence.add(0);
        examination_one_01.next(examination_one_01.state);
        System.out.println(examination_one_01.result);
    }

    /**
     * 这个方法的作用：
     *                  就是从当前状态（currentState）可以扩展的所有子状态（不管胡不合法）。
     *                  就是从当前状态我们可以进行的操作
     * @param currentState
     */
    public void next(int[] currentState){
        //用来表示人现在的位置，从而确定下一步向哪里移动
        int person = currentState[0];
        //表示所有的可以扩展的状态
        for(int i=0;i<currentState.length;i++){
            //这个表示只有人移动，没有承载任何东西
            if(i==0){
                //人移动了
                currentState[0]=1-currentState[0];
                //获得新的状态
                int newState=getHashCode(currentState);
                //表示终止状态
                if(newState==ExaminationOne01.END_STATE){
                    sequence.add(END_STATE);
                    result.add(sequence.stream().collect(Collectors.toList()));
                    sequence.remove(sequence.size()-1);
                    currentState[0]=1-currentState[0];
                    continue;
                }
                if(validate(currentState)){
                    sequence.add(newState);
                    next(currentState);

                }
                currentState[0]=1-currentState[0];
            }
            //这个表示除了人移动了，还带了第i个东西
            else if(currentState[i]==person){
                currentState[0]=1-currentState[0];
                currentState[i]=1-currentState[i];
                int newState=getHashCode(currentState);
                if(newState==END_STATE){
                    sequence.add(END_STATE);
                    result.add(sequence.stream().collect(Collectors.toList()));
                    sequence.remove(sequence.size()-1);
                    currentState[0]=1-currentState[0];
                    currentState[i]=1-currentState[i];
                    continue;
                }
                if(validate(currentState)){
                    sequence.add(newState);
                    next(currentState);
                }
                currentState[0]=1-currentState[0];
                currentState[i]=1-currentState[i];
            }
        }
        sequence.remove(sequence.size()-1);
    }

    /**
     * 这个方法的作用：
     *                  用于判断状态是不是合法，有没有违反约束条件。
     *                  如果违反约束条件就返回：false
     *                  如果没有违反约束条件就返回：true
     * @param currentState
     * @return
     */
    public boolean validate(int[] currentState){
        //用于表示人在哪一个方法，如果人在河岸，就看看河对岸是不是违反约束条件，或者重复，
        //                          如果人在河对岸，就看看河岸是不是违反约束条件
        int hashCode = getHashCode(currentState);
        //如果是重复的状态，就直接返回false
        if(sequence.contains(hashCode)){
            return false;
        }
        //判断是不是违反约束
        int person = currentState[0];
        List<Integer> constraint = IntStream.range(1, currentState.length).filter(i -> currentState[i] != person).sorted().boxed().collect(Collectors.toList());
        if(constraint.size()==1){
            return true;
        }else if(constraint.size()==3){
            return false;
        }else{
            return constraint.get(0)+1!=constraint.get(1);
        }
    }

    /**
     * 这个方法的作用：
     *                  就是从当前状态获取到唯一确定的值。
     *                  我们的计算方法是：currentState[0]*2^0+currentState[1]*2^1+currentState[2]*2^2+currentState[3]*2^3
     *                  也就是计算二进制数的currentState的十进制数。
     *                  即0000---》1111，从0到15，一共16重状态
     * @param currentState
     * @return
     */
    public int getHashCode(int[] currentState){
        return IntStream.range(0,currentState.length).map(i->currentState[i]*(1<<i)).reduce(0,(a,b)->a+b);
    }

}
